package class19;

/**
 * @author YZY
 * @since 2022/8/20 11:37
 * <a href="https://leetcode.cn/problems/longest-common-subsequence/">1143. 最长公共子序列</a>
 * 尝试从右往左的模型，只去管 str1[0...i] 和 str2[0...j] 的最长公共子序列有多长
 * 样本对应模型，考虑当前的结尾，如何考虑可能性
 */
public class Code04_LongestCommonSubsequence {

    // 暴力递归
    public static int longestCommonSubsequence1(String text1, String text2) {
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        return process1(str1, str2, str1.length - 1, str2.length - 1);
    }

    private static int process1(char[] str1, char[] str2, int i1, int i2) {
        if (i1 == 0 && i2 == 0) {
            return str1[i1] == str2[i2] ? 1 : 0;
        }
        if (i1 == 0) {
            return str1[i1] == str2[i2] ? 1 : process1(str1, str2, i1, i2 - 1);
        }
        if (i2 == 0) {
            return str1[i1] == str2[i2] ? 1 : process1(str1, str2, i1 - 1, i2);
        }
        // 下面是当 i1 != 0 && i2 != 0 的情况
        int case1 = process1(str1, str2, i1 - 1, i2);
        int case2 = process1(str1, str2, i1, i2 - 1);
        // 可以考虑i1和i2，也可以不考虑i1和i2，这两种考虑的可能性的交集，包含了都在考虑中
        int case3 = str1[i1] == str2[i2] ? 1 + process1(str1, str2, i1 - 1, i2 - 1) : 0;
        return Math.max(case3, Math.max(case1, case2));
    }

    // 记忆化搜索
    public static int longestCommonSubsequence2(String text1, String text2) {
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int[][] dp = new int[str1.length + 1][str2.length + 1];
        return process2(str1, str2, str1.length - 1, str2.length - 1, dp);
    }

    private static int process2(char[] str1, char[] str2, int i1, int i2, int[][] dp) {
        if (dp[i1][i2] != 0) {
            return dp[i1][i2];
        }
        if (i1 == 0 && i2 == 0) {
            return str1[i1] == str2[i2] ? 1 : 0;
        }
        if (i1 == 0) {
            return str1[i1] == str2[i2] ? 1 : process2(str1, str2, i1, i2 - 1, dp);
        }
        if (i2 == 0) {
            return str1[i1] == str2[i2] ? 1 : process2(str1, str2, i1 - 1, i2, dp);
        }
        // 下面是当 i1 != 0 && i2 != 0 的情况
        int case1 = process1(str1, str2, i1 - 1, i2);
        int case2 = process1(str1, str2, i1, i2 - 1);
        // 可以考虑i1和i2，也可以不考虑i1和i2，这两种考虑的可能性的交集，包含了都在考虑中
        int case3 = str1[i1] == str2[i2] ? 1 + process1(str1, str2, i1 - 1, i2 - 1) : 0;
        return dp[i1][i2] = Math.max(case3, Math.max(case1, case2));
    }

    // 动态规划
    public static int longestCommonSubsequence3(String text1, String text2) {
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int[][] dp = new int[str1.length][str2.length];
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i2 = 1; i2 < str2.length; ++i2) {
            dp[0][i2] = str1[0] == str2[i2] ? 1 : dp[0][i2 - 1];
        }
        for (int i1 = 1; i1 < str1.length; ++i1) {
            dp[i1][0] = str1[i1] == str2[0] ? 1 : dp[i1 - 1][0];
        }
        for (int i1 = 1; i1 < str1.length; ++i1) {
            for (int i2 = 1; i2 < str2.length; ++i2) {
                int case1 = dp[i1 - 1][i2];
                int case2 = dp[i1][i2 - 1];
                int case3 = str1[i1] == str2[i2] ? 1 + dp[i1 - 1][i2 - 1] : 0;
                dp[i1][i2] = Math.max(case3, Math.max(case1, case2));
            }
        }
        return dp[str1.length - 1][str2.length - 1];
    }

}
